package com.frank.leetcode.question_6_10;

import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/zigzag-conversion/description/
 * 6. Z字形变换
 * 难度: 中等
 * <p>
 * 将字符串 "PAYPALISHIRING" 以Z字形排列成给定的行数：
 * <p>
 * P   A   H   N
 * A P L S I I G
 * Y   I   R
 * 之后从左往右，逐行读取字符："PAHNAPLSIIGYIR"
 * 实现一个将字符串进行指定行数变换的函数:
 * string convert(string s, int numRows);
 * 示例 1:
 * <p>
 * 输入: s = "PAYPALISHIRING", numRows = 3
 * 输出: "PAHNAPLSIIGYIR"
 * 示例 2:
 * <p>
 * 输入: s = "PAYPALISHIRING", numRows = 4
 * 输出: "PINALSIGYAHRPI"
 * 解释:
 * <p>
 * P     I    N
 * A   L S  I G
 * Y A   H R
 * P     I
 * <p>
 * <p>
 * Created by zhy on 2018/8/1.
 */
public class Convert_Z {
    private static Logger LOG = LoggerFactory.getLogger(Convert_Z.class);

    @Test
    public void run() {
        System.out.println(convert("0123456789", 3));
    }

    private String convert(String s, int numRows) {
        if (numRows <= 1) return s;

        List<char[]> list = new ArrayList<>();

        int index = 0;
        while (index < s.length()) {
            for (int i = 0; i < numRows - 1; i++) {
                char[] line = new char[numRows];
                if (i == 0) {
                    for (int j = 0; j < numRows; j++) {
                        if (index == s.length()) break;
                        line[j] = s.charAt(index);
                        index++;
                    }
                } else {
                    if (index == s.length()) break;
                    line[numRows - i - 1] = s.charAt(index);
                    index++;
                }

                list.add(line);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < list.size(); j++) {
                char m = list.get(j)[i];
                if (m != 0) {
                    sb.append(m);
                }
            }
        }

        return sb.toString();
    }

    /**
     * 最佳解。获取规律，直接拼接
     *
     * @param s
     * @param numRows
     * @return
     */
    public String convertBest(String s, int numRows) {
        if (numRows < 2) {
            return s;
        }
        StringBuilder result = new StringBuilder();
        int group = 2 * numRows - 2;
        for (int i = 1; i <= numRows; i++) {
            int interval = 2 * numRows - 2 * i;
            if (i == numRows) {
                interval = 2 * numRows - 2;
            }
            int index = i;
            while (index <= s.length()) {
                result.append(s.charAt(index - 1));
                index += interval;
                interval = group - interval;
                if (interval == 0) {
                    interval = group;
                }
            }
        }
        return result.toString();
    }
}